package leetcode

import kotlinetc.println

//https://leetcode.com/problems/find-all-anagrams-in-a-string/
/**
 * Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.
 */

fun main(args: Array<String>) {
    FindAllAnagramsinaString().findAnagrams("abab",
            "ab").println()
}

class FindAllAnagramsinaString {

    fun findAnagrams(s: String, p: String): List<Int> {
        val result = arrayListOf<Int>()
        val len = p.length
        val table = Array('z'.toInt() + 1, { 0 })
        //记录每个字母出现的次数
        p.forEach {
            table[it.toInt()]++
        }
        for (i in 0 until s.length) {
            val end = i + len - 1
            if (end > s.length) break
            val count = table.copyOf()
            var success = true
            for (j in i until end) {
                if (--count[s[j].toInt()] < 0) {
                    success = false
                    break

                }
            }
            if (success)
                result.add(i)
        }
        return result
    }
}
